package 华为OD机试真题2023.基础题;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;
import utils.MyUtil;

public class HJ32_租车骑绿道 {
  public static void main(String[] args) throws FileNotFoundException {
    // 方法一：暴力匹配，O(n^2)
    Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/基础题/input/32.txt"));
    MyUtil.START();
    int W = in.nextInt();
    int N = in.nextInt();
    Integer[] weight = new Integer[N];
    for (int i = 0; i < N; i++) {
      weight[i] = in.nextInt();
    }
    Arrays.sort(
        weight,
        (a, b) -> {
          return b - a;
        });
    int res = 0;
    for (int i = 0; i < N; i++) {
      if (weight[i] == 0) {
        continue;
      }
      res++;
      for (int j = i + 1; j < N; j++) {
        if (weight[j] == 0) {
          continue;
        }
        if (weight[i] + weight[j] > W) {
          continue;
        } else if (weight[i] + weight[j] <= W) {
          weight[j] = 0;
        }
      }
    }
    System.out.println(res);
    MyUtil.END();

    // 方法二：双指针，O(n)
    //    Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/基础题/input/32.txt"));
    //    MyUtil.START();
    //    int W = in.nextInt();
    //    int N = in.nextInt();
    //    int[] weight = new int[N];
    //    for (int i = 0; i < N; i++) {
    //      weight[i] = in.nextInt();
    //    }
    //    Arrays.sort(weight);
    //    int left = 0, right = N - 1;
    //    int res = 0;
    //    int tmp_weight = weight[left] + weight[right];
    //    while (left < right) {
    //      if (tmp_weight > W) {
    //        right--;
    //        res++;
    //        tmp_weight = weight[left] + weight[right];
    //      } else {
    //        left++;
    //        right--;
    //        res++;
    //        tmp_weight = weight[left] + weight[right];
    //      }
    //    }
    //    res++; // 最后还有个left==right，即一个人的情况
    //    System.out.println(res);
    //    MyUtil.END();
  }
}
